//
// Created by littlebear on 2022/3/20.
//

#include <iostream>

using namespace std;

long long moves = 0;

// Hanoi
void hanoi(int n, char a, char b, char c) {
    // Move n disks from a to c using b
    if (n == 1) {
        moves++;
//        printf("Move disk %d from %c to %c\n", n, a, c);
    } else {
        hanoi(n - 1, a, c, b);
        moves++;
//        printf("Move disk %d from %c to %c\n", n, a, c);
        hanoi(n - 1, b, a, c);
    }
}

int main() {
    for (int i = 3; i <= 100; i++) {
        moves = 0;
        clock_t start = clock();
        hanoi(i, 'A', 'B', 'C');
        clock_t end = clock();
        printf("%d disks need %lld moves, time spent: %lf s\n", i, moves, (double)(end - start) / CLOCKS_PER_SEC);
    }
    return 0;
}